1. Field of the Invention
The present invention generally relates to optically encoded symbologies, and more particularly relates to methods and systems for guiding a scanning device to decode 2D symbols.
2. Description of the Related Art
In today""s high-technology world, more and more operations are performed automatically by computers. This increasing demand for automation has created strong demands for new technologies. Bar-code is one of the technologies used for automating data entry.
A bar-code symbol is a pattern containing a series of bars of various widths and spaced apart from one another by spaces of various widths, the bars and spaces have different light reflective properties representing strings of binary ones and zeros. Bar-code symbols are printed directly on a substance or on labels attached to the object. The bar-code symbols are typically read by optical techniques, such as laser beams, Charge-Coupled Device (CCD) or Contact Image Sensor (CIS) cameras. A typical laser-based bar-code reader uses a photo-sensor to convert bars and spaces into an electrical signal as it moves across a bar-code. The reader then measures the relative widths of bars and spaces, translates the different pattern back into regular characters, and sends them on to a computer or portable terminal for further processing. There is a minimum width for these bars and spaces to be decoded properly by scanners. The minimum width is called a xe2x80x9cunitxe2x80x9d or xe2x80x9cmodulexe2x80x9d. The spaces and bars are multiples of the xe2x80x9cunitxe2x80x9d or xe2x80x9cmodulexe2x80x9d.
The conventional bar-code described above is one-dimensional. The information encoded in one-dimension (1D) bar-code is represented only by the widths of bars and spaces, which extends in a single dimension. All the bars and spaces have a uniform height in their vertical direction, thus the information only stored in the horizontal direction of a 1D bar-code. Generally a 1D bar-code is widely used as indices to associate physical objects with larger database containing detailed information. Because of the single dimension, 1D bar-code can only store very limited amount of information, for example, a zip code, a social security number or a serial number.
As the demand for information technologies grows, there is a strong interest in eliminating the associated database and storing more information into the symbology itself. As a result of this demand, the two-dimensional (2D) bar-code technologies have emerged from the extension of the 1D bar-code. The 2D bar-code symbologies are generally square or rectangular patterns that encode data in two dimensions. They fall into two general categories: xe2x80x9cstacked bar-codexe2x80x9d is constructed like a layer cake of 1D bar-code stacked one on top of another; xe2x80x9cmatrix bar-codexe2x80x9d is built on a true two dimensional matrix.
One of the most commonly used xe2x80x9cstacked bar-codexe2x80x9d is PDF417 as shown in FIG. 1A. The detailed descriptions of PDF417 can be found in U.S. Pat. No. 5,304,786. PDF417 contains a number of code segments. Each consists of 4 bars and 4 spaces with total width of 17 modules, hence the name PDF417. It has a high tolerance for damaged symbology when high level of error correction is built in the symbol. Theoretically PDF417 can store up to 2000 characters per symbol, however, the practical limit is no more than 350 characters. It is required to print PDF symbol with high resolution printer such as laser or thermal transfer printers. PDF417 can be read by cameras (CCD or CMOS), and a modified handheld laser or CIS scanner.
QR Code (Quick Response Code) is an example of a xe2x80x9cmatrix barcodexe2x80x9d developed by Nippondenso ID Systems. As shown in FIG. 1B, a QR Code symbol is square in shape and can easily be identified by its finder pattern of nested alternating dark and light squares at three corners of the symbol. Due to the finder pattern, a QR Code symbol can be read very rapidly with CCD array cameras. The drawback is the size, which is 177 modules squared maximum. The corresponding maximum storage capacity is 2956 bytes with encoded with 750 bytes lowest level error correction code.
Scanners based on CCD or CIS cameras are particularly suitable for reading a 2D bar-code. Generally, scanners convert light (which human can see) into 0s and 1s (which a computer can process). In other words, scanners convert data from analogue format into digital format. All scanners work on the same principle of reflectance or transmission. A scanning object to be scanned is placed before a scanner which comprises a light source and a sensor. The amount of light reflected by or transmitted through the scanning object is picked up by the sensor and then converted to a signal proportional to the light intensity.
One of the factors affecting the scanner performance is the scan resolution. The scan resolution relates to the fineness of detail that a scanner can achieve, and is usually measured in dots per inch (dpi). The more dots per inch a scanner can resolve, the more detail the resulting image will have. A scanner typically has a photoelement for each pixel. A scanner claiming a horizontal optical resolution of 600 dpi is alternatively referred to as 600 pixels per inch (ppi), and this is also referred as scanner""s x-direction resolution. For a scanner having a maximum scanning width of 8.5 inches, there is an array of 5100 photoelements in the scan head. The scan head is mounted on a transport which is moved across a scanning object. Although the process may appear to be a continuous movement, the head moves a fraction of an inch at a time, taking a reading between each movement. The number of physical elements in a sensor array determines the horizontal sampling rate and the number of steps per inch determines the vertical sampling rate, which is referred as scanner""s y-direction resolution. The scanner""s resolution is based on its x-direction and y-direction resolutions.
It would be desirable to have a new 2D bar-code with following characteristics: storing much more information, built-in redundancy, multiple levels of damage protection, flexible width and length symbol, and allowing hand-held line-based contact or non-contact scanning.
With proliferation of hand-operating scanning devices, it is preferred to scan a 2D bar-code with hand-held scanners. However, there exist a few problems. A phenomena known as the loss of vertical synchronization 200 in scanning 2D bar-code symbols due to the limited height of elements is shown in FIG. 2. A 2D bar-code 210 is overlapped with a set of parallel scan lines 220. Generally, the angle between scan line 220 and the horizontal axis of the bar-code 210 is non-zero for a hand-held scanning device. Due to the limited height of bar-code elements, certain scan lines 230 cut across two rows of bar-code elements. As a result, these scan lines 230 are not useful. It would be desirable to have a method to decode the 2D bar-code avoiding the loss of synchronization problem. It would also be desirable to decode the 2D bar-code efficiently and effectively.
This section is for the purpose of summarizing some aspects of the present invention and to briefly introduce some preferred embodiments. Simplifications or omissions may be made to avoid obscuring the purpose of the section. Such simplifications or omissions are not intended to limit the scope of the present invention.
The present invention is related to processes, methods, systems and software products to encoding and decoding of a 2D bar-code. In one aspect of the present invention, a new 2D bar-code symbology is presented with at least the following features: 1) variable symbol width and height; 2) variable print resolution; 3) multiple damage protection levels; 4) large information storage; 5) high redundancy; 6) readable by line based scanning devices; and 7) recognizable by either contact scanning or non-contact scanning devices.
According to one embodiment, a 2D bar-code comprises a top border, a bottom border, a left border, a right border, a bit-stream data area and a plurality of data segment dividers. The unique pattern of the top and the bottom border is used for guiding scanning device to recognize the orientation of a 2D bar-code, whether the bar-code is upside down or flipped mirror image. A plurality of corresponding pair of positioning holes on the left and the right border are used for a scanning device to calculate the coordinates of data elements. The bit-stream data area contains bar-code information in the form of ordered rows of 9-bit xe2x80x9ccodewordxe2x80x9d, which has a data structure of 3 rows by 3 columns of data elements as shown in FIG. 3. The order of bits is stored in row major from left to right, then top to bottom.
The width and length of a 2D bar-code is controlled by the amount of information carried in the bit-stream data area. A number of measures to protect against physical damage are employed in the 2D bar-code. The first measure is to divide the data bit-stream into a number of equal size data segments. A set of data segment control information is added to each data segment. As a result, redundancy is provided by repeating the critical control information related to the entire bar-code in each data segment.
One of the measures is to employ an industry standard error correction method (e.g., Reed-Solomon function) in each data segment. So even a portion of a bar-code is not recognizable, the error correction may be able to recreate the missing information with the error correction codeword located in the intact portion of the bar-code. There are a number of different levels of error correction. Depending upon the applicable circumstance, a suitable level of error correction may be chosen. Ensuring higher confidence for decoding, an independent error correction scheme is employed for the data segment control information. Instead of storing codewords in sequential order, codewords are stored in an interleaved order, so the contiguous data is spread out in a larger area. As a result, the chance of damage to contiguous data decreases, while increasing the chance to recreate damage data via error correction.
When a large concentration of bars (dark color) in one particular portion of a bar-code occurs, the scanning device may not catch the few white spaces in this concentration. To protect against this problem, a masking or bitwise-XOR operation is performed between the bit-stream of codeword data and a predefined mask to hide some of the concentrated bars.
In another aspect of the present invention, different decoding methods are also disclosed. One of the methods is used to decode the 2D bar-code after the entire 2D bar-code symbol is scanned and stored. Another one of the methods is used for decoding the 2D bar-code while the 2D bar-code is being scanned. According to one embodiment, these decoding methods are incorporated as a software product loaded on a scanning device for decoding the 2D bar-code efficiently and effectively.
In still another aspect of the present invention, a set of equally spaced parallel positioning lines is attached to a 2D bar-code. These positioning lines are used for guiding the scanning device to decode the 2D bar-code properly.
In still yet another aspect of the present invention, the 2D bar-code may be divided by visible marks corresponding to different paragraphs of an article.
One of the objects, features, and advantages of the present invention is to provide a symbology with flexible features and suitable for scanning.
Other objects, features, and advantages of the present invention will become apparent upon examining the following detailed description of an embodiment thereof, taken in conjunction with the attached drawings.